package com.github.yangyishe.p200;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 118. 杨辉三角
 * https://leetcode.cn/problems/pascals-triangle/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 *
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 *
 *
 *
 *
 * 示例 1:
 *
 * 输入: numRows = 5
 * 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
 * 示例 2:
 *
 * 输入: numRows = 1
 * 输出: [[1]]
 *
 *
 * 提示:
 *
 * 1 <= numRows <= 30
 */
public class Problem118 {
    public static void main(String[] args) {
        int numRows=5;

        Problem118 problem118 = new Problem118();
        List<List<Integer>> generate = problem118.generate(numRows);
        System.out.println("generate = " + generate);
    }

    /**
     * 思路：
     * 一层一层顺序加即可，没有什么难点
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> resultList=new ArrayList<>();
        List<Integer> firstList= Arrays.asList(1);
        resultList.add(firstList);
        for(int i=1;i<numRows;i++){
            List<Integer> lastList=resultList.get(resultList.size()-1);
            List<Integer> tmpList=new ArrayList<>(i+1);
            tmpList.add(1);
            for(int j=1;j<i;j++){
                int left=lastList.get(j-1);
                int right=lastList.get(j);
                tmpList.add(left+right);
            }
            tmpList.add(1);
            resultList.add(tmpList);
        }

        return resultList;
    }
}
